/*
 * @lc app=leetcode.cn id=23 lang=javascript
 *
 * [23] 合并K个排序链表
 *
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/description/
 *
 * algorithms
 * Hard (46.82%)
 * Likes:    269
 * Dislikes: 0
 * Total Accepted:    28.9K
 * Total Submissions: 61.7K
 * Testcase Example:  '[[1,4,5],[1,3,4],[2,6]]'
 *
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * 
 * 示例:
 * 
 * 输入:
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 * 
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (lists.length === 0) return null
  if (lists.length === 1) return lists[0]
  if (lists.length === 2) return mergeTwoLists(lists[0], lists[1])

  let mid = Math.floor(lists.length / 2)
  let l1 = new Array(mid)
  let l2 = new Array(lists.length - mid)

  for (let i = 0; i < mid; i++) {
    l1[i] = lists[i]
  }
  for (let i = 0, j = mid; j < lists.length; i++, j++) {
    l2[i] = lists[j]
  }
  
  return mergeTwoLists(mergeKLists(l1), mergeKLists(l2))
}

function mergeTwoLists (l1, l2) {
  let root = new ListNode(null)
  let cur = root
  while (l1 != null && l2 != null) {
    if (l1.val < l2.val) {
      cur.next = l1
      cur = cur.next
      l1 = l1.next
    } else {
      cur.next = l2
      cur = cur.next
      l2 = l2.next
    }
  }
  if (l1 == null) cur.next = l2
  else cur.next = l1

  return root.next
}

